\subsection{Funcionamiento del kernel}

\subsubsection{Administración del procesador}
Desde la versión 2.6 hasta la 2.6.23, el kernel usa un scheduler \textit{O(1)}, mientras que desde la versión 2.6.23 el kernel usa un \textit{Completely Fair Scheduler} que utiliza 
árboles rojo-negro en lugar de colas.\\
El scheduler del kernel 2.6 (hasta la versión 2.6.23) fue diseñado por Ingo Molnar. Ingo ha estado involucrado en el desarrollo del kernel de Linux desde 1995.
Su motivación fue diseñar e implementar un nuevo scheduler que fuera O(1) para el overhead del cambio de contexto, iterrupciones por timer, y wakeup. 
Una de las causas que llevó al desarrollo de este tipo de scheduler fue el creciente uso de la máquina virtual de Java (JVM), ya que ésta hace uso intensivo de muchos 
threads, que resulta en una gran pérdida de eficiencia con un scheduler O(n).\\
Veamos ahora las estructuras básicas que maneja el scheduler. Cada CPU tiene una cola de listos (\textit{runqueue}), compuesta por 140 listas de prioridad, en las cuales 
las tareas son agregadas según el orden FIFO (\textit{First In First Out}). Las tareas nuevas son agregadas a las listas según su prioridad, y a cada tiene asignada una cantidad 
de tiempo limitada para su ejecución. Las primeras 100 son reservadas para tareas de tiempo real con un quantum de aproximadamente 200ms, mientras que el resto para tareas de usuario, 
con un quantum de 10ms.\\

\begin{center}
  \includegraphics[totalheight=0.3\textheight]{./imagenes/figure1_linux_scheduler.png}
\end{center}

En conjunto con la cola de listos, o de procesos a ejecutar (\textit{active runqueue}), hay también una lista de expirados. Cuando una tarea usa todo su quantum, es movida a la cola de expirados. 
Durante el cambio, su quantum es recalculado (y por lo tanto su prioridad). Cuando la cola de tareas activas se vacía, se intercambian todos los punteros y la nueva cola pasa a ser 
la que antes era la de expirados.\\
El trabajo del scheduler es simple: elegir las tareas de las listas de prioridad más altas y ponerlas a ejecutar. Para realizar esto eficientemente, se usa un bitmap para definir cuando una 
tarea esta en una determinada lista de prioridad. Por lo tanto, en la mayoría de las arquitecturas, se usa una instrucción de \textit{find-first-bit-set} para encontrar la prioridad más 
alta en una de 5 palabras de 32 bits (para las 140 prioridades). Esto hace que el tiempo que toma encontrar la próxima tarea a ejecutar no dependa de la cantidad de tareas, sino de la cantidad 
de prioridades, haciendo que las operaciones de schedule se realizen en un tiempo acotado.\\
Otra de las ventajas con la que cuenta el scheduler de Linux 2.6 es el desalojo, lo cual impide que se de la situación en la que una tarea de prioridad baja ejecute mientras tareas 
de prioridad más alta estén esperando para ser ejecutadas. De darse esta situación, la tarea que está siendo ejecutada es desalojada y vuelta a poner en su lista de prioridad, para su posterior 
ejecución.\\
El punto anterior da lugar a pensar que puede existir el efecto de inanición para tareas de muy baja prioridad, ya que estarán siendo desalojadas por tareas de mayor prioridad constantemente.
El scheduler de Linux evita esta situación penalizando las tareas atadas a CPU y premiando a aquellas ataras a E/S, para que de esta forma poco a poco incrementen su prioridad y poder ejecutar 
en algún momento. Esto se conoce como \textit{Dynamic task prioritization}.\\
El \textit{Completely Fair Scheduler} es el nombre del nuevo scheduler que introdujo la versión 2.6.23 del kernel de Linux. Su principal objetivo es maximizar el desempeño de las tareas interactivas. 
El trabajo de Con Kolivan sobre CPU scheduling inspiró a Ingo Molnar a desarrollar este nuevo scheduler, como reemplazo al O(1). En contraste con su versión anterior, el nuevo scheduler no esta basado 
en colas, sino que utiliza árboles rojo-negro para implementar una línea de tiempo para la ejecución futura de las tareas. Adicionalmente, el scheduler usa una granularidad de nanosegundos en lugar de milisegundos.
Como su antecesor, CFS utliza el concepto de ``sleeper fairness'' (algo asi como igualdad para los que duermen), que considera a los procesos dormidos o en espera equivalentes a aquellos que están en la 
cola de ejecución. Esto significa que los procesos interactivos que pasan gran parte de su tiempo esperando respuestas del usuario obtengan una parte de tiempo de procesamiento considerable cuando la necesitan.

\subsubsection{Administración de memoria}
El subsistema de administración de memoria (de ahora en más \textit{MMS} por Memory Management Subsystem) es una de las partes más importantes de cualqueir sistema operativo. A continuación se explica brevemente 
dicho subsistema para el kernel de Linux, asumiendo que se tiene conocimiento de ciertos términos y mecanismos que son propios de una administración de memoria paginada por demanda.\\
Si bien Linux utiliza paginación como mecanismo de administración de memoria, en muchas arquite
Linux asume que existen tres niveles de tablas de páginas. Cada nivel accedido contiene el número de page-frame del próximo nivel de las tablas. La siguiente figura muestra cómo se descompone 
una dirección virtual para acceder a las diferentes tablas

\begin{center}
  \includegraphics[totalheight=0.4\textheight]{./imagenes/page-tables.png}
\end{center}

Las traducciones de direcciones corren por cuenta del procesador, al cual se le provee la dirección de dichas tablas para poder realizar el proceso.
Cada plataforma en la que linux corre debe proveer las macros correspondientes que permitan al kernel traducir las tablas al formato particular del procesador, y de esta forma evitar 
que el kernel tenga que conocer la forma en la que trabaja la arquitectura.
Esta forma de trabajar ha probado ser exitosa, permitiendo que el kernel pueda correr tanto en procesadores Alpha que utilizan tres niveles, como en procesadores Intel x86, que utilizan sólo 2.\\
Durante la ejecución del sistema existen numerosos pedidos del sistema trantando de ubicar páginas físicas de memoria. Por ejemplo cuando un programa es cargado, el sistema operativo busca y reserva la 
cantidad de páginas físicas que considere necesarias, reservándolas para la ejecución del programa, y liberándolas cuando éste termine.
El mecanismo y las estructuras de datos usadas para la adquisición y liberación de páginas es posiblemente uno de los más críticos del sistema, y por lo tanto deben funcionar con la mayor eficiencia posible.\\
Linux utiliza el algorítmo \textit{Buddy}\footnote{http://en.wikipedia.org/wiki/Buddy\_memory\_allocation} para adquirir y liberar bloques de páginas.
El código que realiza la adquisición de páginas intenta conseguir uno o más bloques de páginas físicas. Las páginas son reservadas en bloques cuyo tamaño es potencia de 2. Esto significa que se puede 
reservar 1 página, 2 páginas, 4 páginas, y asi siguiendo. Mientras haya suficiente espacio libre en la memoria física, el algorítmo continuará buscando en el área de memoria libre por bloques para satisfacer 
la demanda. Para ello existe un arreglo llamado justamente \textit{free\_area}. Cada posición del arreglo contiene un mapa de memoria que describe bloques de páginas, cuyo tamaño se corresponde con la posición 
del arreglo. Por ejemplo, la posición 2 del arreglo contiene información sobre bloques de 4 páginas, tanto libres como ocupados.
El algorítmo primero busca bloques de páginas del tamaño pedido, y de no encontrar continúa buscando bloques más grandes, hasta encontrar alguno libre. Si el bloque encontrado es mayor 
al tamaño que originalmente se quería, entonces éste es partido en bloques menores para evitar desperdiciar memoria. Como su tamaño es potencia de 2, simplemente se va partiendo a la mitad hasta que se 
encuentra el tamaño deseado. El resto de los bloques es encolado en las posiciones del arreglo que corresponden según su tamaño, y el bloque adquirido es devuelto al que lo solicitó.

\begin{center}
  \includegraphics[totalheight=0.4\textheight]{./imagenes/free-area.png}
\end{center}

La adquisición de bloques de páginas tiende a fragmentar la memoria cuando grandes bloques de memoria son divididos en pequeños para satisfacer algún pedido. Para evitar este efecto, 
el código encargado de la liberación recombina las páginas libres en bloques más grandes (cuando puede por supuesto).
Cuando un bloque de páginas se libera, el bloque adyacente o \textit{buddy block} del mismo tamaño es chequeado para ver si esta libre o no. En caso afirmativo, son combinados en un nuevo bloque. 
Cada vez que esto sucede, se intenta combinar el nuevo bloque en uno más grande. De esta forma los tamaños de los bloques son tan grandes como lo permita la memoria.\\

Hasta ahora hemos descrito el tratamiento de la memoria física. Ahora hablaremos sobre la memoria virtual, y cómo linux la administra.\\
Cuando un programa es ejecutado, su contenido (es decir, el código) debe ser traido al espacio de direcciones virtuales del proceso. Lo mismo ocurre con librerías compartidas, o cualquier dato que el proceso 
requiera. Sin embargo, la información no es traída a la memoria física inmediatamente, sino que es \textit{linkeada} a la memoria virtual del proceso. Luego cuando dicha información es referenciada, 
entonces sí se produce la carga a memoria física, pero no antes. Este mecanismo de linkeo a la memoria virtual de un proceso se conoce como \textit{memory mapping}.\\
Una vez que la imagen del ejecutable ha sido linekada dentro del espacio de direcciones virtuales del proceso, entonces puede comenzar a ejecutar. Ni bien comience a ejecutar, intentará acceder a 
direcciones virtuales que aún no se encuentran en memoria física. Esto ocasioará que el procesador reporte un \textit{page fault} a Linux, describiendo qué dirección virtual ocasionó el error, y qué 
tipo de acceso fue. Linux guarda en ciertas estructuras llamadas \textit{vm\_area\_struct} las distintas áreas de memoria virtual linkeadas al espacio de direccionamiento del proceso. En el momento 
del page fault el kernel debe buscar a qué área corresponde la dirección virtual que ocasionó el problema, para luego cargar la información en memoria física. Dado que esta búsqueda es crítica en cuanto 
al tiempo que demore (recordemos que un programa genera durante su ejecución una importante cantidad de page faults), las estructuras \textit{vm\_area\_struct} están organizadas en un árbol AVL. 
En caso de que no exista un área asociada a la dirección virtual, entonces el proceso ha efecutado una lectura ilegal, y es terminado. Luego chequea que el acceso sea válido (se podría intentar leer una zona 
cuya lectura no está permitida). En caso de que se considere un page fault legal, entonces se debe resolver.\\
Para ello Linux debe diferenciar entre qué páginas se encuentran en la partición \textit{swap} (espacio del disco usado para alojar las páginas que son desalojadas de memoria física) y cuales no han sido 
cargadas aún desde el archivo original del ejecutable. Para ello se apoya en la entrada de las tablas de páginas. Si la entrada no está vacía, pero es inválida, entonces hay que ir a buscar a la partición swap. 
En caso contrario debe traerse desde el archivo orignal.\\
Finalmente hablaremos de cómo Linux decide la liberación de espacio en memoria física cuando ésta se encuentra demasiado llena.\\
Cuando la memoria física se vuelve escasa, el \textit{MMS} debe intentar hacer lugar. Esta tarea es realizada lanzando un proceso (un deamon) llamado \textit{kswapd}.
Este proceso es un tipo de proceso especial, un \textit{kernel thread}. Los \textit{kernel threads} no tienen memoria virtual. Ejecutan en modo kernel directamente sobre la memoria física. 
El kernel swap daemon esta mal nombrado asi, ya que no sólo se encarga de guardar páginas en la partición swap, sino que se asegura que haya una cantidad suficiente de páginas libres en el sistema para garantizar 
que el \textit{MMS} pueda operar en forma eficiente. El kernel swap daemon se inicia junto con el proceso init durante el inicio del sistema, y se ejecuta periódicamente (\textit{kernel swap timer}). 
Cada vez que se agota el kernel swap timer, el swap daemon revisa las páginas libres para controlar si su cantidad se esta agotando. Hace uso de dos 
variables: \textit{free\_pages\_high} y \textit{free\_pages\_low} para decidir si debería liberar espacio. Mientras la cantidad de páginas libres este por encima de \textit{free\_pages\_high}, el proceso 
no realiza nada. Por el contrario, si la cantidad ha caído por debajo de \textit{free\_pages\_high}, entonces se intentarán las siguiente estrategias:
\begin{itemize}
  \item Reducir el tamaño del buffer y page cache. (No hemos hablado de esto, pero existe un cache para agilizar las lecturas de disco)
  \item Desalojar las páginas compartidas del System V (Mecanismo de comunicación entre procesos)
  \item Desalojar páginas.
\end{itemize}
Para la liberación de páginas, el daemon revisa los procesos para determinar cuales de ellos son buenos candidatos para ser desalojados (sus páginas, no confundir con scheduling). Aquellos que son 
candidatos son los que hacen uso de páginas que pueden ser desalojadas. Si esto es así, dichas páginas serán guardadas en la partición \textit{swap} sólo cuándo no exista una mejor forma de reconstruir la 
información (por ejemplo, el código de un ejecutable nunca se guarda en swap ya que puede ser leído nuevamente desde el archivo original). \\
Linux usa el algorítmo de \textit{Aging}\footnote{http://es.wikipedia.org/wiki/Algoritmos\_de\_reemplazo\_de\_p\%C3\%A1ginas\#Ejemplos\_.28Aging.29} (envejecimiento) para decidir cuáles páginas libera. 
Cada vez que una página es referenciada, su edad se incrementa en 3, hasta un máximo de 20, mientras que cada vez que el kernel swap daemon controla dicho valor, se decrementa en 1. 
Cuando una página tiene edad 0, entonces el daemon intentará, verificando su estado \textit{dirty}, liberar dicha página guardándola en el swap o no.

\subsubsection{Sisetma de archivos}
El sisteam de archivos por defecto que usa Linux desde la versión del kernel 2.4.15 es \textit{\textbf{ext3}}.
Fue desarrollado por Stephen Tweedie, y fue presentado cerca de 1998 como el sucesor de ext2 (del mismo autor), introduciendo \textit{registro por diario}, o 
\textit{journaling}\footnote{Un sistema de archivos con journaling incorpora diario sobre el cual se realizan los cambios antes de realizarlos efectivamente sobre el file system principal. Este tipo de 
file systems tienen menos pobrabilidades de corromperse en caso de una falla de suministro de energía o un system crash.\\ http://www.ibm.com/developerworks/library/l-journaling-filesystems/index.html} \\
Aunque su velocidad y escalabilidad es menor que sus competidores, como JFS, ReiserFS o XFS, tiene la ventaja de permitir actualizar de ext2 a ext3 sin perder los datos almacenados ni tener que formatear 
el disco. Tiene un menor consumo de CPU y esta considerado mas seguro que otros sistemas de ficheros en Linux dada su relativa sencillez y su mayor tiempo de prueba.\\
El sistema de archivo ext3 agrega a ext2 lo siguiente:
\begin{itemize}
  \item Registro por diario.
  \item Índices en árbol para directorios que ocupan múltiples bloques.
  \item Crecimiento en línea.
\end{itemize}

\textbf{Tamaño de archivos} \\ \\
\begin{tabular}{| l | l | l |}\hline
Tamaño del bloque & Tamaño máximo de los archivos & Tamaño máximo del sistema de ficheros \\\hline
1 KiB & 16 GiB & $<$2 TiB \\
2 KiB & 256 GiB & $<$4 TiB \\
4 KiB & 2 TiB & $<$8 TiB \\
8 KiB & 2 TiB &	$<$16 TiB \\
\hline
\end{tabular}
\\ \\
\textbf{Niveles de journaling} \\ \\
Hay tres niveles posibles de Journaling (registro por diario)
\begin{itemize}
  \item \textit{Diario (riesgo bajo)}: Los metadatos y los ficheros de contenido son copiados al diario antes de ser llevados al sistema de archivos principal. Como el diario esta en el disco continuamente puede mejorar el rendimiento en ciertas ocasiones. En otras ocasiones el rendimiento es peor porque los datos deben ser escritos dos veces, una al diario y otra a la parte principal del sistema de archivos.
  \item \textit{Pedido (riesgo medio)}: Solo los metadatos son registrados en el diario, los contenidos no, pero está asegurado que el contenido del archivo es escrito en el disco antes de que el metadato asociado se marque como transcrito en el diario. Es el sistema por defecto en la mayoría de las distrubuciones de Linux. Si hay un bajón de tensión o kernel Panic cuando el fichero se está escribiendo o esta empezando, el diario indicará que el nuevo archivo o el intento no ha sido pasado, por lo que sera purgado por el proceso de limpiado
  \item \textit{Reescritura (riesgo alto)}: Solo los metadatos son registrados en el diario, el contenido de los archivos no. Los contenidos pueden estar escritos antes o despues de que el diario se actualice. Como resultado, los archivos modificados correctamente antes de una ruptura pueden volverse corruptos. Por ejemplo, un archivo pendiente de ser marcado en el diario como mayor de lo que actualmente es, convirtiendo en basura al final de la comprobación. Las versiones antiguas de los archivos pueden aparecer inesperadamente despues de una recuperación de diario. La carencia de sincronización entre los datos y el diario es rápidamente subsanada en muchos casos. JFS usa este nivel de journaling, pero se asegura de que cualquier basura es borrada al reiniciar    
\end{itemize}
 
Algunas desventajas del sistema de archivos ext3 son: 
\begin{itemize}
 \item \textit{Funcionalidad}: Como ext3 esta hecho para ser compatible con ext2, la mayoria de las estructuras del archivación son similares a las del ext2. Por ello, ext3 carece de muchas caracteristicas de los diseños mas recientes como las extensiones, la localización dinamica de los inodos, y la sublocalización de los bloques. Hay un limite de 31998 subdirectorios por cada directorio, que se derivan de su limite de 32 links por inodo. Ext3, como la mayoría de los sistemas de archivos actuales de Linux, no puede ser chequeado por el fsck mientras el sistema de archivos esta montado para la escritura. Si se intenta chequear un sistema de ficheros que esta montado puede detectar falsos errores donde los datos no han sido volcados al disco todavía, y corromper el sistema de archivos al intentar arreglar esos errores.
 \item \textit{Desfragmentación}:No hay herramienta de desfragmentación online para ext3 que funcione en nivel del sistema de archivos. Existe un desfragmentador offline para ext2, e2defrag, pero requiere que el sistema de archivos ext3 sea reconvertido a ext2 antes de iniciarse. Pero dependiendo de los bits encendidos en el sistema, e2defrag puede destruir datos. No sabe como tratar la mayoría de las nuevas caracteristicas de ext3. Hay herramientas de usuario para desfragmentar como Shake y Defrag. Shake trabaja localizando para todo el archivo como una operación, lo que generalmente causa que el localizador encuentre espacio continuo en el disco. También intenta escribir archivos usados al mismo tiempo que otros. Defrag trabaja copiando cada archivo sobre si mismo. De todas formas solo funcionan si el sistema de archivos esta razonablemente vacio. No existe una verdadera herramienta de desfragmentacion para ext3. Como se viene diciendo, la guia de administracion de Linux dice: "Los modernos sistemas de archivos de Linux mantienen la fragmentacion al minimo manteniendo los bloques de un archivo juntos, aunque no puedan ser guardados en sectores consecutivos. Algunos sistemas de archivos, como ext3, localizan efectivamente los bloques libres mas cercanos a otros en el archivo. Por ello no es necesario preocuparse por la fragmentación en un sistema de Linux" Mientras ext3 es más resistente a la fragmentacián que Fat, nada evita que los sistemas ext3 se puedan fragmentar con el tiempo. Consecuentemente el sucesor de ext3, ext4, incluye una utilidad de desfragmentación y soporte para extensiones (regiones contiguas del fichero).
 \item \textit{Compresión}: El soporte para la compresión esta disponible como un parche no oficial para ext3. Este parche es un porte directo de e2compr pero necesita un mayor desarrollo ya que todavía no implementa el journaling. El actual parche es llamado e3compr y puede ser bajado aqui: [1]
 \item \textit{No hay comprobacion en el diario}: Ext3 no hace la suma de verificación cuando esta escribiendo en el diario. Si barrier = 0 no esta habilitado como una opcion de montaje, y si el hardware esta escribiendo fuera de la orden, se corre el riesgo de una corrupcion muy amplia del sistema de archivos en caso de que haya un fallo repentino del hardware.
\end{itemize}
